//实现 strStr() 函数。 
//
// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如
//果不存在，则返回 -1 。 
//
// 说明： 
//
// 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 
//
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 
//
// 
//
// 示例 1： 
//
// 
//输入：haystack = "hello", needle = "ll"
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：haystack = "aaaaa", needle = "bba"
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= haystack.length, needle.length <= 10⁴ 
// haystack 和 needle 仅由小写英文字符组成 
// 
// Related Topics 双指针 字符串 字符串匹配 👍 1452 👎 0


import java.util.Arrays;

/**
 * [0028]实现 strStr()-ImplementStrstr
 * <p>
 * 算法: BF 算法、Rabin-Karp 算法、Boyer-Moore 算法、Knuth-Morris-Pratt 算法、Sunday 算法
 * <br>
 * 时间复杂度: O(1)
 * <br>
 * 空间复杂度: O(1)
 * <p>
 * 知识点:
 * <br>
 *
 * @author yonxao
 * @since 2022-06-11 18:22:42
 */
@SuppressWarnings("all")
class ImplementStrstr {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int strStr(String haystack, String needle) {
            if (haystack == null || needle == null || haystack.length() < needle.length()) {
                return -1;
            }
            if (needle.length() == 0) {
                return 0;
            }
            int n = haystack.length(), m = needle.length();

            for (int i = 0; i < n - 1 - m; i++) {
                int j;
                for (j = 0; j < m - 1; j++) {
                    if (haystack.charAt(i + j) != needle.charAt(j)) {
                        break;
                    }
                }
                if (j == m) {
                    return i;
                }
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    @SuppressWarnings("all")
    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";
        String haystack1 = "aaaaa", needle1 = "bba";
        String haystack2 = "aaaaa", needle2 = "";
        String haystack3 = "mississippi", needle3 = "issip";

        // System.out.println(bruteForce(haystack, needle));
        System.out.println(bruteForce(haystack, needle));
    }

    /**
     * 算法: 暴力匹配
     * <br>
     * 时间复杂度: O(n*m)
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 知识点: BF 算法(Brute Force)--暴力算法
     * <br>
     */
    public static int first(String haystack, String needle) {
        int n1 = haystack.length();
        int n2 = needle.length();

        out:
        for (int i = 0; i < n1; i++) {
            if (haystack.charAt(i) == needle.charAt(0) && (n1 - i) >= n2) {
                for (int j = 0; j < n2; j++) {
                    if (haystack.charAt(i + j) != needle.charAt(j)) {
                        continue out;
                    }
                }
                return i;
            }
        }
        return -1;
    }

    /**
     * 算法: BF 算法
     * <br>
     * 时间复杂度: O((n-m)*m)
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 知识点: 无
     * <br>
     */
    public static int firstOptimize(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        // 特殊情况
        if (n < m) {
            return -1;
        }
        if (m == 0) {
            return 0;
        }

        int length = n - m + 1;
        outer:
        for (int i = 0; i < length; i++) { // time n-m
            for (int j = 0; j < m; j++) { // time m
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    continue outer;
                }
            }
            return i;
        }
        return -1;
    }


    /**
     * 算法: Brute Force 算法
     * <br>
     * 时间复杂度: O((n-m)*m)
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 知识点: 无
     * <br>
     */
    public static int bruteForce(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        // 特殊情况
        if (n < m) {
            return -1;
        }
        if (m == 0) {
            return 0;
        }

        int length = n - m + 1, j;
        for (int i = 0; i < length; i++) { // time n-m
            for (j = 0; j < m; j++) { // time m
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 算法: KMP(Knuth-Morris-Pratt) 算法
     * <br>
     * 时间复杂度: O(n+m)
     * <br>
     * 空间复杂度: O(m)
     * <p>
     * 知识点: KMP
     * <br>
     */
    public static int strStr(String haystack, String needle) {
        if (haystack == null || needle == null || haystack.length() < needle.length()) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }
        int n = haystack.length(), m = needle.length();

        int[] next = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }


}


/**
 * 算法: 通用 Rabin-Karp 算法, 模式串和所有主串的子串计算 hashcode 进行对比
 * <br>
 * 时间复杂度: O((n-m)m)
 * <br>
 * 空间复杂度: O(1)
 * <p>
 * 知识点:
 * <br>
 * rk字符串匹配算法, 主要引入了hash的概念, 利用子串的hash值依次对比主串相应长度的子串hash值, 并对hash值相同的子串进行匹配对比
 * <p>
 * 缺点: hash 算法的字符集处理哈希冲突无法避免
 */
@SuppressWarnings("all")
class RabinKarpSearch {

    /**
     * rk算法入口
     *
     * @param haystack 主字符串
     * @param needle   模式串
     * @return 子串在主串中的索引位置
     */
    public static int rk(String haystack, String needle) {
        // 字符串非法判定
        if (haystack == null || needle == null || needle.length() > haystack.length()) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }

        int n = haystack.length(), m = needle.length();
        // 计算子串hash值
        int hash = hash(needle, 0, m, 26, 31); // time m
        for (int i = 0; i < n - m + 1; i++) { // time n-m
            // 对主串内的数字一次进行hash计算，并对比子串是否匹配
            if (hash(haystack, i, m, 26, 31) == hash // time m
                    && match(haystack, needle, i)) {  // time m
                return i;
            }
        }
        return -1;
    }

    /**
     * 自定义 hash 算法
     *
     * @param s     要计算的串
     * @param start 串的开始位置
     * @param len   串的长度
     * @param r     进制数
     * @param k     将字符串映射到k的范围
     * @return hashcode
     */
    private static int hash(String s, int start, int len, int r, int k) {
        int hash = 0;
        for (int i = start; i < start + len; i++) { // time m
            // 进制系数 与 hash 的积 + 每个字符与范围取余的结果
            hash = (r * hash + s.charAt(i) % k);
        }
        // 将最后的结果，映射到指定范围内
        return hash % k;
    }

    /**
     * 对于hash计算结果相同的两个子串，是否匹配的比较
     * 主要判定hash冲突情况下的匹配问题
     *
     * @param t 主串
     * @param p 模式串
     * @param i 从主串下标为i的地方开始比较
     * @return 匹配结果
     */
    private static boolean match(String t, String p, int i) {
        for (int j = 0; j < p.length(); j++) { // time m
            if (p.charAt(j) != t.charAt(j + i)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";

        int i = RabinKarpSearch.rk(haystack, needle);
        System.out.println(i);
    }
}


/**
 * 算法: Rabin-Karp 算法, 哈希算法优化
 * <br>
 * 时间复杂度: O(n)
 * <br>
 * 空间复杂度: O(n)
 * <p>
 * 知识点:
 * <br>
 * 一遍遍历算所有子串的 hashcode
 */
@SuppressWarnings("all")
class RabinKarpSearchOptimize {

    /**
     * rk算法入口
     *
     * @param haystack 主字符串
     * @param needle   模式串
     * @return 子串在主串中的索引位置
     */
    public static int rabinKarp(String haystack, String needle) {
        // 字符串非法判定
        if (haystack == null || needle == null || needle.length() > haystack.length()) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }

        int n = haystack.length(), m = needle.length(), count = n - m + 1;

        // 存储每个子串的 hashcode
        int[] hashCodes = new int[count]; // space n-m
        // 模式串的 hashcode
        int hashCode = hashCode(needle, m, 0);
        // 第一个子串的 hashcode
        hashCodes[0] = hashCode(haystack, m, 0);

        // 一遍遍历计算出所有子串的 hashCode
        for (int i = 1; i < count; i++) { // time n-m
            hashCodes[i] = arrHashCode(hashCodes[i - 1], haystack, i, m); // time 1
        }

        for (int i = 0; i < count; i++) { // time n-m
            if (hashCode == hashCodes[i] // time 1
                    && match(haystack, needle, i)) { // time m
                return i;
            }
        }
        return -1;
    }

    private static int hashCode(String s, int length, int start) {
        int system = 26; // 进制
        int code = 0;

        for (int i = start; i < length + start; i++) {
            code = code * system + (s.charAt(i) - 'a');
        }
        return code;
    }

    private static int arrHashCode(int prevHashCode, String haystack, int i, int m) {
        int prevChar = (haystack.charAt(i - 1) - 'a');
        int lastChar = (haystack.charAt(i + m - 1) - 'a');
        int system = 26; // 进制
        int prevCharPower = m - 1; // 前一个字符的幂

        int repeat = (prevHashCode - prevChar * (int) Math.pow(system, prevCharPower)) * system;
        return repeat + lastChar;
    }


    private static boolean match(String t, String p, int start) {
        for (int i = 0; i < p.length(); i++) { // time m
            if (p.charAt(i) != t.charAt(i + start)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";

        int i = RabinKarpSearchOptimize.rabinKarp(haystack, needle);
        System.out.println(i);
    }
}


/**
 * 算法: Boyer-Moore 算法, 坏字符, 好后缀
 * <br>
 * 时间复杂度: 不好分析
 * <br>
 * 空间复杂度: 不好分析
 * <p>
 * 知识点:
 * <br>
 * 1. 预处理模式串
 * 2. 好后缀求后缀子串, 每个字符和尾巴对比, 让后从尾巴倒着对比
 */
class BoyerMooreSearch {

    /**
     * 创建一个数组用来保存模式串中每一个字符在模式串中最后一次出现的位置
     * <p>
     * 用来求坏字符情况下移动位数
     */
    private static int[] generateBadCharArr(char[] patternArr, int m) {
        int[] badCharArr = new int[256];
        // 都初始化为 -1, 代表模式串中不存在这个字符
        for (int i = 0; i < 256; ++i) {
            badCharArr[i] = -1;
        }
        // 如果有两个相同字符, 则后面那个的位置会覆盖前面那个
        for (int i = 0; i < m; ++i) {
            int ascii = patternArr[i];
            badCharArr[ascii] = i; // 下标
        }
        return badCharArr;
    }

    /**
     * suffix，prefix 数组事先申请好
     * <br>
     * 什么是好后缀: 已经和模式串匹配的后缀子串, 在模式串的剩余部分又出现了, 这个后缀串就是好后缀
     * <br>
     * 好后缀, 将已经匹配过的部分利用起来, 用来求好后缀条件下的移动位数
     * <br>
     * 好后缀数组: 已经和模式串匹配的后缀子串, 在模式串的剩余部分出现的位置
     * 前缀子串数组: 好后缀是否同样是前缀子串
     *
     * @param suffix 模式串的后缀子串; 下标:后缀子串的长度; 值:在模式串 的前部中 跟好后缀{u}相匹配的子串{u*}的起始下标值。
     * @param prefix 模式串的后缀子串是否是模式串的前缀子串
     */
    private static void generateGoodSuffix(char[] patternArr, int m, int[] suffix, boolean[] prefix) {
        // 初始化
        for (int i = 0; i < m; ++i) { // time 2m
            suffix[i] = -1;
            prefix[i] = false;
        }

        // [c, a, b, c, a, b]
        for (int i = 0; i < m - 1; i++) { // patternArr[0, i]  // time m
            int j = i;
            // 后缀子串长度
            int k = 0;

            while (j >= 0 && patternArr[j] == patternArr[m - 1 - k]) { // 与 patternArr[0, m-1] 求后缀子串 // time m
                --j;
                ++k;
                suffix[k] = j + 1; // j+1表示公共后缀子串在b[0, i]中的起始下标  // [-1, 2, 1, 0, -1, -1]
            }
            if (j == -1) {
                prefix[k] = true; // 如果后缀子串也是前缀子串  // [false, false, false, true, false, false]
            }
        }
    }


    /**
     * 好后缀规则计算移动位数
     *
     * @param j      坏字符对应模式串字符的下标
     * @param m      模式串长度
     * @param suffix 后缀子串在模式串中的好后缀起始位置
     * @param prefix 后缀子串同时是否是前缀子串
     * @return 移动位数
     */
    private static int goodSuffixMove(int j, int m, int[] suffix, boolean[] prefix) {
        // 好后缀长度
        int k = m - 1 - j;
        // 如果含有长度为 k 的好后缀, 返回移动位数
        if (suffix[k] != -1) {
            return j - suffix[k] + 1; // +1 的原因是要放移动到坏字符之后
        }
        // 找头部为好后缀子串的最大长度，从长度最大的子串开始
        for (int r = j + 2; r <= m - 1; ++r) {  // (r = j + 2) : j 是坏字符, j+1是好后缀, j+2是好后缀的后缀子串的起始
            // 如果是头部
            if (prefix[m - r]) {
                return r;
            }
        }
        // 如果没有发现好后缀匹配的串，或者头部为好后缀子串，则移动到 m 位，也就是匹配串的长度
        return m;
    }


    /**
     * 主流程
     */
    private static int bm(char[] textArr, int n, char[] patternArr, int m) {
        // 构建坏字符哈希表, 每一个字符在模式串中最后出现的位置
        int[] badCharArr = generateBadCharArr(patternArr, m); // time charset+m  space charset

        // 构建好后缀哈希表
        int[] suffix = new int[m]; // space m
        boolean[] prefix = new boolean[m]; // space m
        generateGoodSuffix(patternArr, m, suffix, prefix); // time 2m + m^2

        int i = 0; // 第一个匹配字符
        while (i <= n - m) { // time n-m
            int j;
            // 从后往前匹配，匹配失败，找到坏字符
            for (j = m - 1; j >= 0; --j) {
                if (textArr[i + j] != patternArr[j]) {
                    break;
                }
            }
            // 模式串遍历完毕，匹配成功
            if (j < 0) {
                return i;
            }
            // 坏字符匹配失败, 求出坏字符规则下移动的位数，即[坏字符下标] - [模式串对应字符的最右下标]
            int x = j - badCharArr[textArr[i + j]];
            // 好后缀情况: 求出好后缀移动位数, 如果不含有好后缀的话, 则按照坏字符来
            int y = 0;
            if (y < m - 1 && m - 1 - j > 0) { // (y < m - 1) 至少有两个字符
                y = goodSuffixMove(j, m, suffix, prefix);
            }
            // 移动好后缀和坏字符之间的最大位
            i = i + Math.max(x, y);
        }
        return -1;
    }


    /**
     * 入口
     */
    public static int strStr(String haystack, String needle) {
        // 字符串非法判定
        if (haystack == null || needle == null || needle.length() > haystack.length()) {
            return -1;
        }
        if (needle.length() == 0) {

            return 0;
        }

        int n = haystack.length(), m = needle.length();
        char[] textArr = haystack.toCharArray();
        char[] patternArr = needle.toCharArray();

        return bm(textArr, n, patternArr, m);
    }

    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";

        int i = BoyerMooreSearch.strStr(haystack, needle);
        System.out.println(i);
    }

}


/**
 * 算法: KMP 算法, 坏字符, 好前缀 (双指针:主串和模式串各一个指针, 当模式串指针移动到末尾, 表示找到了)
 * <br>
 * 时间复杂度: O(n+m)
 * <br>
 * 空间复杂度: O(m)
 * <p>
 * 知识点:
 * <br>
 * 1. 预处理 next 数组
 */
@SuppressWarnings("all")
class KMP {

    /**
     * 入口
     */
    public static int strStr(String haystack, String needle) {
        // 字符串非法判定
        if (haystack == null || needle == null || needle.length() > haystack.length()) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }

        int n = haystack.length(), m = needle.length();
        char[] textArr = haystack.toCharArray();
        char[] patternArr = needle.toCharArray();

        return kmp(textArr, n, patternArr, m);
    }


    private static int kmp(char[] text, int n, char[] pattern, int m) {
        int[] next = getNexts(pattern, m);
        System.out.println(Arrays.toString(next));

        int j = 0; // 模式串的索引
        for (int i = 0; i < n; ++i) { // 主串索引, 遍历主串  // time n

            // 发现不匹配的字符, 根据 next 数组移动模式串指针, 移动到公共前缀的后一位
            while (j > 0 && text[i] != pattern[j]) {
                j = next[j - 1] + 1;
            }

            // 字符相同, 模式串指针往后移动
            if (text[i] == pattern[j]) {
                ++j;
            }
            if (j == m) { // 找到匹配模式串的了
                return i - m + 1;
            }
        }
        return -1;
    }


    private static int[] getNexts(char[] pattern, int m) {
        int[] next = new int[m]; // space m

        next[0] = -1; // 1 个字符的时候直接过
        int k = -1;

        for (int i = 1; i < m; ++i) { // 遍历模式串 time m
            while (k != -1 && pattern[k + 1] != pattern[i]) {
                k = next[k];
            }
            if (pattern[k + 1] == pattern[i]) {
                ++k;
            }
            next[i] = k;
        }

        return next;
    }


    public static void main(String[] args) {
        String haystack = "hello world", needle = "cabcab";

        // next [-1, -1, -1, 0, 1, 2]
        int i = KMP.strStr(haystack, needle);
        System.out.println(i);
    }

}